#include <iostream>
#include <climits>
#include <LEDA/graphics/graphwin.h>
#include <LEDA/graphics/color.h>
#include <LEDA/system/basic.h>
#include "control.h"
#include <cmath>

#include <LEDA/core/p_queue.h>
#include <LEDA/graph/node_map.h>
#include <LEDA/graph/node_array.h>

using namespace leda;
using std::cout;
using std::endl;

#define DIRECTED true

/**
 * Get edge weight of a given edge e
 */
double get_edge_weight(GraphWin & gw , edge e)
{
	string edge_label = gw.get_user_label(e);
	double weight = atof(edge_label.c_str());
	return weight;
}

/**
 * Dijkstra's algorithm to compute shortest paths in a directed graph.
 */
void dijkstra(node &start , graph &g, GraphWin &gw)
{
	// unknown distance from source to v (initialized to infinity)
	node_array<double> dist(g,INFINITY);
	// previous node in optimal path from source
	node_array<node> from(g,NULL);

	// distance from source to source
	dist[start] = 0.0;
	// set label with distance
	gw.set_user_label(start , string("%g" , dist[start]));

	//store all pq_items for quick access for updates etc.
	node_array<bin_heap_item> node_pq_pointer(g , NULL);

	//marks the presence of a node in the tree
	node_array<bool> marker(g, false);

	//Color the starting node
	gw.set_color(start , blue);

	//priority queue for all nodes adjacent to our tree
	p_queue<double, edge> priority_queue;

	edge e_iter;

	forall_out_edges(e_iter, start) {
		//insert the edge into the priority queue
		bin_heap_item it = priority_queue.insert(get_edge_weight(gw, e_iter) , e_iter);
		gw.set_color(e_iter , green);
		gw.set_color(g.opposite(e_iter , start) , green);
		control_wait(0.5);
		//save the pq_item in a map for quick access through the target node
		node target = g.opposite(e_iter, start);
		node_pq_pointer[target] = it;
		//node start is the first node in our tree. Therefore we mark it as visited.
		marker[start] = true;
	}

	//pop edges from the priority queue and add them to our tree.
	//after that check all its neighbors and update the priority queue

	while(!priority_queue.empty())
	{
		edge e = priority_queue.inf(priority_queue.find_min());
		double path_length = priority_queue.prio(priority_queue.find_min());

		// delete item from priority queue
		priority_queue.del_min();

		//see which side of the edge is not yet marked
		node target = g.opposite(target, e);
		if (marker[target])
		{
			target = g.opposite(target, e);
		}

		//add edge to shortest path tree
		control_wait(0.5);
		gw.set_color(e, blue);
		gw.set_width(e, 3);
		gw.set_color(target, blue);
		gw.set_color(g.opposite(target, e), blue);
		gw.set_user_label(target , string("%g" , path_length));
		control_wait(0.5);

		// mark target as visited
		marker[target] = true;

		dist[target] = path_length;
		from[target] = g.opposite(e , target);

		// unset the pointer from target to its pq_item (it is gone anyway)
		node_pq_pointer[target] = NULL;

		// now we need to update the priority queue with the neighbors of target
		edge adj_edge;

		forall_out_edges(adj_edge, target)
		{
			node neighbour = g.opposite(adj_edge, target);

			// ignore self-loops and nodes that are marked
			if ((neighbour != target) && (!marker[neighbour]))
			{
				// get the priority queue item.
				bin_heap_item node_item = node_pq_pointer[neighbour];

				double new_distance = dist[target] + get_edge_weight(gw , adj_edge);
				// if item exists check if we have to update it
				// else we add a new item to the list
				if (node_item != NULL)
				{
					if (priority_queue.prio(node_item) > new_distance)
					{
						// replace the current edge with the 'better' edge
						priority_queue.change_inf(node_item, adj_edge);
						priority_queue.decrease_p(node_item, new_distance);

						edge neighbor_edges;
						forall_inout_edges(neighbor_edges , neighbour) {
							gw.set_color(neighbor_edges , grey3);
						}
						gw.set_color(adj_edge , green);
						gw.set_color(neighbour , green); //not really needed, just making sure it is green..
					}
				}
				else
				{
					// if the node is not yet in our queue we add it
					// and add the reference in the node_pq_pointer map
					bin_heap_item new_item = priority_queue.insert(new_distance, adj_edge);

					node_pq_pointer[neighbour] = new_item;

					// finally we color it to indicate that this is a adjacent edge
					// which will be considered in the next round
					gw.set_color(adj_edge , green);
					gw.set_color(neighbour , green);
					control_wait(0.5);
				}

			} // end if (neighbor != target && !marker[neighbor])

		} // end forall_inout_edges

	} // end while

}

int main(int argc, char *argv[])
{
    GraphWin gw(800, 600);
    gw.display();
    create_control();
    // set environment to display a directed / undirected graph depending on the DIRECTED constant
    gw.set_directed(DIRECTED);
    if (argc > 1)
        gw.read(argv[1]);
    gw.edit();
    graph &g = gw.get_graph();
    if (g.number_of_nodes() == 0) {
        gw.close();
        destroy_control();
        exit(1);
    }

    // initialize graph nodes and edges as grey3
    node v;
    edge e;
    forall_nodes(v, g)
    {
        gw.set_label_type(v, user_label);
        gw.set_color(v, grey3);
    }
    forall_edges(e, g)
    {
        gw.set_color(e, grey3);
    }

    while ((v = gw.read_node()) == NULL) ;

    //run dijkstra algorithm
    dijkstra(v , g , gw);

    gw.acknowledge("Ready!");
    gw.edit();
    gw.close();
    destroy_control();
    exit(0);
}
